#pragma once
#include "Graph.hpp"
#include "set"
template<class V,class E>
class Graph;

template<class V ,class E = double >
class UnDirGraph: public  Graph<V,E>
{
public:
    E m_empty; //设置默认的零值
    UnDirGraph()=default;
    explicit UnDirGraph(std::vector<V> v,E empty = 0)
    {
        m_empty = empty;
        for(auto & p : v) {
            std::map<V,E> tmp;
            m_data[p]= tmp;
        }
    }

    explicit UnDirGraph(Graph<V,E> G)
    {
        m_empty = G.m_empty;
        auto Nodes = G.getNodes();
        // 分配空间
        for(auto & p : Nodes) {
            std::map<V,E> tmp;
            m_data[p]= tmp;
        }
        // 转换为无向图
        for(auto [key1,value1] : G.m_data)
        {
            for(auto [key2,value2] : value1)
            {
                m_data[key1][key2] = value2;
                m_data[key2][key1] = value2;
            }
        }
    }
    // 比较函数
    bool operator == (UnDirGraph<V,E> G2)
    {
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                if( m_data[key1][key2] != G2.m_data[key1][key2] ){
                    return false;
                }
            }
        }
        return true;
    }

    void addEdge(V v1, V v2,E e) override
    {
        m_data[v1][v2] = e;
        m_data[v2][v1] = e;
    }

    void addEdgesFrom(std::vector<V>  vec1, std::vector<V>  vec2 , E e) override
    {
        if(vec1.size() != vec2.size()) {
            throw std::invalid_argument("vec1 ,vec2 大小不一致");
        }
        for(int i = 0; i < vec1.size() ; i++){
            m_data[vec1[i]][vec2[i]] = e;
            m_data[vec2[i]][vec1[i]] = e;
        }
    }
    std::vector<V> getNodes()
    {
        std::vector<V> nodes(m_data.size());
        auto iter = m_data.begin();
        for(int i = 0; i < m_data.size();i ++){
            nodes[i] = iter->first;
            iter ++;
        }
        return nodes;
    }
    bool write2Dot(const std::string& filename) override
    {
        std::fstream outFile;
        outFile.open(filename,std::ios::out);
        // 检查文件是否成功打开
        if (!outFile) {
            std::cerr << "无法打开文件" << std::endl;
            return false;  // 返回错误代码
        }

        outFile << "graph G { \n node [shape=ellipse, color=blue, style=filled, fontcolor=white];\n"
                   "    edge [color=gray]; \n";

        auto nodes = this->getNodes();
        std::set<V> record; //防止重复画图
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                if( record.find(key2) == record.end()){
                    outFile << key1 << "--" << key2<<"[label="<<value2 << "]\n";
                }
            }
            record.insert(key1);
        }

        outFile << "\n }";
        outFile.close();
        return true;
    }
    void print()override
    {
        for(auto [key1,value1] : m_data){
            std::cout<<"[" << key1 << ", ";
            for(auto [key2,value2]: value1){
                    std::cout << key2 << ":"<< value2 << " ";
            }
            std::cout << "]\n";
        }
    }
    bool is2NodesConnected(V v1, V v2)
    {
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::queue<V> que ; //保存需要遍历的节点
        que.push(v1);
        while(!que.empty()){
            flag[que.front()] = 1; //已经访问当前的节点
            for(auto [key,value] : m_data[que.front()]){
                if(flag[key] == 0){
                    que.push(key);
                    flag[key] = 1;
                    if(key == v2){
                        return true;
                    }
                }
            }
            que.pop();
        }
        return false;
    }
    // Prim算法是无向图里面独有的,有向图需要做对称化操作
    UnDirGraph<V,E> Prim()
    {
        // Prim算法,算法思路是迭代N-1次,每一次选择最短的路径
        auto Nodes = getNodes();
        int N = Nodes.size();
        UnDirGraph<V,E> min_tree(Nodes);
        std::vector<V> min_tree_nodes = {Nodes[0]}; //选择第一个节点插入
        for(int i = 0;i < N-1 ;i ++)
        {
            PrimPriorityQueue<V,E> primPriQue;
            for(auto node: min_tree_nodes){
                for(auto [key,value] : m_data[node]){
                    if( std::find(min_tree_nodes.begin(),min_tree_nodes.end(),key) == min_tree_nodes.end() ){ //链接的另一个节点不是在min_tree_nodes里面
                        primPriQue.push(PrimData<V,E>(node,key,value));
                    }
                }
            }
            auto topNode = primPriQue.top();
            min_tree_nodes.push_back(topNode.m_node2);
            min_tree.addEdge(topNode.m_node1,topNode.m_node2,topNode.m_dist);
        }

        return min_tree;
    }
    bool isGraphConnected() override
    {
        // 判断图是否连通
        std::vector<V> Nodes = getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::stack<V> sta; //栈数据结构
        sta.push(Nodes[0]);
        flag[Nodes[0]] = 1;
        int count = 1;
        while(!sta.empty()){
            int End = 0;
            for(auto [key,value] : m_data[sta.top()]){
                if(flag[key] == 0){
                    count ++;
                    flag[key] = 1;
                    sta.push(key);
                    End = 1;
                    break;
                }
            }
            if(End == 0){
                sta.pop(); //弹出元素
            }
        }
        if(count == N){return true;}
        else {return false;}
    }
    void DFS() override //深度优先搜索算法
    {
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::stack<V> sta; //栈数据结构
        sta.push(Nodes[0]);
        flag[Nodes[0]] = 1;
        std::cout << Nodes[0] << ",";
        while(!sta.empty()){
            int End = 0;
            for(auto [key,value] : m_data[sta.top()]){
                if(flag[key] == 0){
                    std::cout << key << ",";
                    flag[key] = 1;
                    sta.push(key);
                    End = 1;
                    break;
                }
            }
            if(End == 0){
                sta.pop(); //弹出元素
            }

        }

    }
    E sumWeight() override
    {
        E sum = 0;
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                sum += m_data[key1][key2];
            }
        }
        return sum/2;
    }
    // Kruskal算法是无向图里面独有的,有向图需要做对称化操作
    UnDirGraph<V,E> Kruskal() //Kruskal的思想是先把全部顶点加进来,逐渐添加边,防止出现连通图的情况.
    {
        auto Nodes = getNodes();
        int N = Nodes.size();
        UnDirGraph<V,E> min_tree(Nodes);
        PrimPriorityQueue<V,E> primPriQue;
        std::set<V> record;
        // 不重复加边
        for(auto[key1,value1]:m_data){
            record.insert(key1);
            for(auto [key2,value2] : value1){
                if( record.find(key2) == record.end()){
                    primPriQue.push(PrimData<V,E>(key1,key2,value2));
                }
            }
        }

        for(int i = 0; i < N-1;i ++){
            while(true){
                auto topData = primPriQue.top();
                primPriQue.pop(); //弹出第一个元素
                if(min_tree.is2NodesConnected(topData.m_node1,topData.m_node2) == false){
                    // 如果被加入的两个点不连通,则添加边
                    min_tree.addEdge(topData.m_node1,topData.m_node2,topData.m_dist);
                    break;
                }
            }
        }
        return min_tree;
    }

protected:
    std::map<V,std::map<V,E>> m_data;

};